#include "GenerateHeightMap.h"
#include "HeightMap.h"

#include <random>

/// Anonymous namespace for auxiliary functions
namespace
  {
  /**
  * CalculateDiamondVals - given the location (x, y) of a diamond centre and a diamond size
  * (i.e. the distance from diamond center to a diamond vertex) calculate a diamond value.
  * @param[in]      i_heightmap     Height map
  * @param[in]      i_x, i_y        Coordinates of a value being calculated (i.e. diamond centre coordinates)
  * @param[in]      i_stride        Diamond stride (i.e. distance between diamond centre and its vertices)
  * @return                         Diamond value
  * 
  * -------------
  * |.    o    .|
  * |           |
  * |o    x    o|
  * |           |
  * |.    o    .|
  * -------------
  * 
  * Here, the diamond centre (value of which is being calculated) is denoted by "x" symbol
  * and diamond vertices are denoted by "o" symbol. The size of a diamond is 1.
  *
  * In order to support tiling generated maps the careful calculation of values that lie on the map
  * edges is needed. The first 4 if-else clauses perform these calculations.
  * The last calculation handles general case (when (x, y) coordinates do not lie on map edge)
  */
  double CalculateDiamondVals(HeightMap& i_heightmap, size_t i_x, size_t i_y, size_t i_stride)
    {
    size_t indices[4][2] = {{i_x, i_y - i_stride}, {i_x, i_y + i_stride}, {i_x - i_stride, i_y}, {i_x + i_stride, i_y}};
    double accumulator = 0.0;

    for (auto i = 0; i < 4; ++i)
      {
      size_t x = indices[i][0];
      size_t y = indices[i][1];
      if (x >= 0 && x < i_heightmap.GetSizeX() && y >= 0 && y < i_heightmap.GetSizeY())
        accumulator += i_heightmap.Get(x, y);
      }

    return accumulator / 4;
    }


  /**
  * CalculateSquareVals - given the location (x, y) of a square centre and a square size
  * (i.e. the distance from square center to square vertex) calculate a square value.
  * @param[in]      i_heightmap     Height map
  * @param[in]      i_x, i_y        Coordinates of a value being calculated (i.e. square centre coordinates)
  * @param[in]      i_stride        Half of square side
  * @return                         Square value
  * 
  * -------------
  * |x    .    x|
  * |           |
  * |.    o    .|
  * |           |
  * |x    .    x|
  * -------------
  * 
  * Here, the square centre (value of which is being calculated) is denoted by "o" symbol
  * and square vertices are denoted by "x" symbol. The stride of a square is 1.
  */
  double CalculateSquareVals(HeightMap& i_heightmap, size_t i_x, size_t i_y, size_t i_half_size)
    {
    return (i_heightmap.Get(i_x - i_half_size, i_y - i_half_size) +
            i_heightmap.Get(i_x - i_half_size, i_y + i_half_size) +
            i_heightmap.Get(i_x + i_half_size, i_y - i_half_size) +
            i_heightmap.Get(i_x + i_half_size, i_y + i_half_size)) / 4;
    }


  /**
  * ScaleHeightMap - multiply every element of height map by positive scalar value
  * @param[in_out]    io_heightmap    Map to be scaled
  * @param[in]        i_scale         Scaling coefficient
  */
  void ScaleHeightMap(HeightMap& io_heightmap, double i_scale)
    {
    for (size_t y = 0; y < io_heightmap.GetSizeY(); ++y)
      for (size_t x = 0; x < io_heightmap.GetSizeX(); ++x)
        io_heightmap.Set(x, y, io_heightmap.Get(x, y) * i_scale);
    }

  /**
  * PerformDiamondStep - performs diamond step of diamond-square algorithm
  * @param[out]   io_heightmap    Height map on which the step is performed
  * @param[in]    i_problem_size  The size of a height map
  * @param[in]    i_stride        Stride length
  * @param[in]    i_jitter        Jitter value
  * @param[in]    i_rng           Pseudo-random number generator
  * @param[in]    i_distribution  Uniform distribution of doubles in range (-1; 1)
  */
  void PerformDiamondStep(HeightMap& io_heightmap, size_t i_problem_size, size_t i_stride, double i_jitter, std::default_random_engine& i_rng, std::uniform_real_distribution<double>& i_distribution)
    {
    double random_increment;
    bool oddline = 0;
    for (size_t x = 0; x <= i_problem_size; x += i_stride)
      {
      oddline = (0 == oddline);
      for (size_t y = 0; y <= i_problem_size; y += i_stride)
        {
        if ((oddline) && (!y))
          y += i_stride;
        random_increment = i_distribution(i_rng);
        io_heightmap.Set(x, y, CalculateDiamondVals(io_heightmap, x, y, i_stride) + i_jitter * random_increment);
        y += i_stride;
        }
      }
    }

  /**
  * PerformSquareStep - performs square step of diamond-square algorithm
  * @param[out]   io_heightmap    Height map on which the step is performed
  * @param[in]    i_problem_size  The size of a height map
  * @param[in]    i_stride        Stride length
  * @param[in]    i_jitter        Jitter value
  * @param[in]    i_rng           Pseudo-random number generator
  * @param[in]    i_distribution  Uniform distribution of doubles in range (-1; 1)
  */
  void PerformSquareStep(HeightMap& io_heightmap, size_t i_problem_size, size_t i_stride, double i_jitter, std::default_random_engine& i_rng, std::uniform_real_distribution<double>& i_distribution)
    {
    double random_increment;
    for (size_t x = i_stride; x < i_problem_size; x += i_stride)
      {
      for (size_t y = i_stride; y < i_problem_size; y += i_stride)
        {
        random_increment = i_distribution(i_rng);
        io_heightmap.Set(x, y, CalculateSquareVals(io_heightmap, x, y, i_stride) + i_jitter * random_increment);
        y += i_stride;
        }
      x += i_stride;
      }
    }
  }

/// Interface implementation

void GeneratedHeightMapWithDiamondSquare(HeightMap& o_heightmap, double i_plains_percentage, double i_max_height)
  {
  std::default_random_engine rng;

  ///Random value in range (-1; 0.5) with uniform distribution
  std::uniform_real_distribution<double> uniform_dist(-1.0, 0.5);

  const size_t problem_size = o_heightmap.GetSizeY() - 1;

  /**
  * Jitter is a surface "irregularity" characteristic.
  * Min value is 0.01, so even when map consists of plains only it's not completely flat
  */
  double jitter = (1.0 - i_plains_percentage) + 0.01;
  if (jitter > 1.0)
    jitter = 1.0;

  /**
  * Rather than make a version of algorithm with 4 recursive calls on every quarter of map,
  * implement iterative version that completes Square step and then Diamond step with some stride,
  * divides that stride by a factor of 2 and repeats previous steps while stride is greater than 0
  */
  size_t stride = problem_size / 2;
  while (stride > 0)
    {
    PerformSquareStep(o_heightmap, problem_size, stride, jitter, rng, uniform_dist);
    PerformDiamondStep(o_heightmap, problem_size, stride, jitter, rng, uniform_dist);

    stride /= 2;
    jitter /= 2;
    }
  ScaleHeightMap(o_heightmap, i_max_height);
  }